package com.zk;

import java.io.PrintWriter;
import java.util.*;

/**
 * 分支界限法解旅行商问题
 * https://blog.csdn.net/mymy_blog/article/details/54619684
 *
 * {{0, 3, 1, 5, 8}, {3, 0, 6, 7, 9},
                 {1, 6, 0, 4, 2}, {5, 7, 4, 0, 3},
                 {8, 9, 2, 3, 0}};
 * {'a', 'b', 'c', 'd', 'e'};
 */
public class TSPProblem implements AlgoInteraction {

    @Override
    public void exec(Scanner scanner, PrintWriter printWriter) {
        printWriter.println("请输入点,以字母表示,每个字母一行,字母 z 表示结束:");

        List<Character> characterList = new ArrayList<>();
        char c = 'z';
        while ( (c = scanner.next().charAt(0)) != 'z' ) {
            characterList.add(c);
        }

        Character[] chs = characterList.toArray(new Character[characterList.size()]);
        printWriter.println("您输入的点集合为:" + characterList);

        HashMap<Character, Integer> chIntMap = new HashMap<Character, Integer>();
        for (int i = 0; i < chs.length; i++) {
            chIntMap.put(chs[i], i);
        }

        int[][] path = new int[characterList.size()][characterList.size()];
        for (int i=0; i<characterList.size(); i++) {
            printWriter.println("请输入点 " + characterList.get(i).charValue() + " 到其它 (包括自身) 点的距离,每行一个整数:");

            for (int j=0; j<characterList.size(); j++) {
                int dist = scanner.nextInt();
                path[i][j] = dist;
            }

        }

        printWriter.println("您输入的距离图为:");
        for (int i=0; i<path.length; i++) {
            for (int j=0; j<path[i].length; j++) {
                if (j == path[i].length - 1) {
                    printWriter.print(path[i][j]);
                } else {
                    printWriter.print(path[i][j] + " ");
                }
            }
            printWriter.println();
        }

        ShortestPath sp = new ShortestPath(path, chIntMap);
        ArrayList<Integer> dotsList = new ArrayList<Integer>();
        dotsList.add(0);

        HashMap<Integer, ArrayList<Line>> linesMap = sp.shortestEdge();

        Node root = new Node(0, 0);
        root.setLines(linesMap);
        root.setDots(dotsList);

        Node bestNode = sp.bestPath(root);
        printWriter.println("最短路径为: " + bestNode.getL());

        for (int i=0; i<bestNode.getDots().size(); i++) {
            if (i == bestNode.getDots().size() - 1) {
                printWriter.print(chs[bestNode.getDots().get(i)]);
            } else {
                printWriter.print(chs[bestNode.getDots().get(i)] + "->");
            }
        }

        printWriter.println();
    }

    public class ShortestPath {
        //记录路径
        int[][] path = null;
        HashMap<Character, Integer> chIntMap = null;

        //记录状态列点表
        PriorityQueue<Node> nodeQueue = null;

        //构造比较函数
        Comparator<Node> comparator = new Comparator<Node>() {
            public int compare(Node o1, Node o2) {
                return o1.getLb() - o2.getLb();
            };
        };

        public ShortestPath(int[][] path, HashMap<Character, Integer> chIntMap) {
            this.path = path;
            this.chIntMap = chIntMap;
            this.nodeQueue = new PriorityQueue<Node>(comparator);
        }

        /**
         * 最优路径
         *
         * @param root
         * @return
         */
        public Node bestPath(Node root) {
            //将开始节点加入队列
            nodeQueue.add(root);
            //记录最优结果
            Node bestNode = root;
            int bestL = Integer.MAX_VALUE;
            //记录当前操作节点
            Node currentNode = null;

            while (!nodeQueue.isEmpty()) {
                currentNode = nodeQueue.poll();
                int index = currentNode.getIndex();
                //获取当前节点所在点的相邻点
                ArrayList<Integer> adjacentPoints = getAdjacentPoints(index);
                for (int i : adjacentPoints) {
                    //当前已被选择点列表
                    ArrayList<Integer> dotsList = currentNode.getDots();
                    if (!dotsList.contains(i)) {
                        //新增节点后所包含的路径
                        ArrayList<Integer> childDotsList = new ArrayList<Integer>();
                        for (int dot : dotsList) {
                            childDotsList.add(dot);
                        }
                        childDotsList.add(i);
                        //判断扩展后是否满足条件b在c前面
                        if (judgeBCconstraint(childDotsList)) {
                            int L = currentNode.getL() + path[index][i];
                            Line middleLine = new Line(index, i, path[index][i]);
                            Node childNode = new Node(L, i);
                            childNode.setDots(childDotsList);
                            //该状态点计算lb边界的线段
                            HashMap<Integer, ArrayList<Line>> linesMap = new HashMap<Integer, ArrayList<Line>>();
                            linesMap = copyHashMap(currentNode.getLines());
                            childNode.setLines(linesMap);
                            //计算新增点后边界
                            childNode.setLb(childNode.computeLb(middleLine));
                            if (childDotsList.size() < path.length) {
                                //有机会成为更优的路径，则加入优先队列
                                if (childNode.getLb() < bestL) {
                                    nodeQueue.add(childNode);
                                }
                            } else {
                                //获取开始点
                                int start = childNode.getDots().get(0);
                                int cost = childNode.getL() + path[i][start];
                                //加入开始节点，作为终点
                                childNode.getDots().add(start);
                                //已经找到一条路径
                                if (bestL > cost) {
                                    bestL = cost;
                                    childNode.setL(cost);
                                    bestNode = childNode;
                                }
                            }
                        }
                    }
                }
            }

            //将最优路径返回
            return bestNode;
        }

        /**
         * 复制Map中的内容
         *
         * @param lines
         * @return
         */
        public HashMap<Integer, ArrayList<Line>> copyHashMap(HashMap<Integer, ArrayList<Line>> lines) {
            HashMap<Integer, ArrayList<Line>> linesMap = new HashMap<Integer, ArrayList<Line>>();
            for (Map.Entry<Integer, ArrayList<Line>> entry : lines.entrySet()) {
                ArrayList<Line> linesList = new ArrayList<Line>();
                for (Line l : entry.getValue()) {
                    Line tempLine = new Line(l.getStart(), l.getEnd(), l.getLength());
                    linesList.add(tempLine);
                }

                linesMap.put(entry.getKey(), linesList);
            }

            return linesMap;
        }

        /**
         * 返回选定点的所有相邻点
         *
         * @param start
         * @return
         */

        public ArrayList<Integer> getAdjacentPoints(int start) {
			//存储相邻节点
            ArrayList<Integer> adjacentPoints = new ArrayList<Integer>();
            int[] arr = path[start];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > 0) {
                    adjacentPoints.add(i);
                }
            }

            return adjacentPoints;
        }

        /**
         * 获取所给图的每个点的最短两条边
         *
         * @return
         */

        public HashMap<Integer, ArrayList<Line>> shortestEdge() {
			//保存每个节点的最短边
            HashMap<Integer, ArrayList<Line>> linesMap = new HashMap<Integer, ArrayList<Line>>();
            for (int i = 0; i < path.length; i++) {
                int min = Integer.MAX_VALUE;
				//保存第一个最近的点
                int firstDot = -1;
				//保存第二个较近的点
                int secondDot = -1;
				//存储一个点的最近两条边
                ArrayList<Line> linesList = new ArrayList<Line>();

                for (int j = 0; j < path[i].length; j++) {
                    if (i == j) {
                        continue;
                    }

                    if (path[i][j] > 0 && min > path[i][j]) {
                        min = path[i][j];
                        firstDot = j;
                    }
                }

                min = Integer.MAX_VALUE;
                Line line = new Line(i, firstDot, path[i][firstDot]);
                linesList.add(line);

				//寻找第二个最近点
                for (int j = 0; j < path[i].length; j++) {
                    if (i == j || j == firstDot) {
                        continue;
                    }

                    if (path[i][j] > 0 && min > path[i][j]) {
                        min = path[i][j];
                        secondDot = j;
                    }
                }

                Line secondLine = new Line(i, secondDot, path[i][secondDot]);
                linesList.add(secondLine);
                linesMap.put(i, linesList);
            }

            return linesMap;
        }

        /**
         * 判断b在c之前的约束是否满足
         *
         * @param dots
         * @return
         */

        public boolean judgeBCconstraint(ArrayList<Integer> dots) {
			//计算字符b对应数值
            int bNum = chIntMap.get('b');

			//计算字符c对应数值
            int cNum = chIntMap.get('c');

			//记录节点b在列表的下标位置
            int bIndex = -2;

			//计算节点c在列表中的下标位置
            int cIndex = -1;

            for (int i = 0; i < dots.size(); i++) {
                if (dots.get(i) == bNum) {
                    bIndex = i;
                }

                if (dots.get(i) == cNum) {
                    cIndex = i;
                }
            }

            if (cIndex < 0) {
                return true;
            } else {
                if (bIndex < 0) {
                    return false;
                } else if (bIndex > cIndex) {
                    return false;
                } else {
                    return true;
                }
            }
        }

    }


    /**
     * 计算最优节点
     *
     * @author ym
     */

    public class Node {
		//最优边界
        int lb = 0;

		//记录长度
        int l = 0;

		//当前点
        int index = 0;

		//记录长度
        ArrayList<Integer> dots = null;

		//记录计算最小边界的边
        HashMap<Integer, ArrayList<Line>> lines = null;

        public Node() {
            dots = new ArrayList<Integer>();
            lines = new HashMap<Integer, ArrayList<Line>>();
        }

        public Node(int l, int index) {
            this.l = l;
            this.index = index;
            dots = new ArrayList<Integer>();
            lines = new HashMap<Integer, ArrayList<Line>>();
        }

        /**
         * 计算新的lb
         *
         * @param line
         * @return
         */

        public int computeLb(Line line) {
			//替换line.start为起点边

            ArrayList<Line> startLinesList = lines.get(line.getStart());
            boolean isExist = containSameLine(startLinesList, line);

            if (!isExist) {
                int index = getLongestLine(startLinesList);
                startLinesList.set(index, line);
            }

			//替换line.end为起点的边
            ArrayList<Line> endLinesList = lines.get(line.getEnd());
            isExist = containSameLine(endLinesList, line);

            if (!isExist) {
                int index = getLongestLine(endLinesList);
                endLinesList.set(index, line);
            }

			//计算新的Lb
            int lb = 0;
            for (Map.Entry<Integer, ArrayList<Line>> entry : lines.entrySet()) {
                for (Line l : entry.getValue()) {
                    lb += l.getLength();
                }
            }

			//向上取整
            lb = lb % 2 == 0 ? (lb / 2) : ((lb + 1) / 2);
            return lb;
        }

        /**
         * 判断边是否包含在集合中
         *
         * @param linesList
         * @param line
         * @return
         */

        public boolean containSameLine(ArrayList<Line> linesList, Line line) {
            for (Line l : linesList) {
                if (l.getStart() == line.getStart()) {
                    if (l.getEnd() == line.getEnd()) {
                        return true;
                    }
                } else if (l.getStart() == line.getEnd()) {
                    if (l.getEnd() == line.getStart()) {
                        return true;
                    }
                }
            }

            return false;
        }

        /**
         * 获取最长边在集合中的下标
         *
         * @param linesList
         * @return
         */

        public int getLongestLine(ArrayList<Line> linesList) {
            int index = 0;
            for (int i = 1; i < linesList.size(); i++) {
                if (linesList.get(i).length > linesList.get(index).length) {
                    index = i;
                }
            }

            return index;

        }

        public int getLb() {
            return lb;
        }

        public void setLb(int lb) {
            this.lb = lb;
        }

        public int getL() {
            return l;
        }

        public void setL(int l) {
            this.l = l;
        }

        public ArrayList<Integer> getDots() {
            return dots;
        }

        public void setDots(ArrayList<Integer> dots) {
            this.dots = dots;
        }

        public HashMap<Integer, ArrayList<Line>> getLines() {
            return lines;
        }

        public void setLines(HashMap<Integer, ArrayList<Line>> lines) {
            this.lines = lines;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

    }


    /**
     * 记录两点
     *
     * @author ym
     */

    static class Line {

		//记录开始点
        int start = 0;

		//记录结束点
        int end = 0;

		//记录长度
        int length = 0;

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getLength() {
            return length;
        }

        public void setLength(int length) {
            this.length = length;
        }

        public Line(int start, int end, int length) {
            this.start = start;
            this.end = end;
            this.length = length;
        }

    }

}
